package class05_归并排序练习题快排.test;

public class Code02_PartitionAndQuickSourt {

    /**
     *  <= partition 左边
     *  > partition 右边
     */
    public static void quickSort1(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    private static void process(int[] arr, int L, int R) {
        if(L >= R){
            return;
        }
        int M = partition(arr, L, R);
        process(arr, L, M - 1);
        process(arr, M + 1, R);
    }

    private static int partition(int[] arr, int L, int R) {
        if (L > R) {
            return -1;
        }
        if (L == R) {
            return L;
        }

        int lessEqual = L - 1;
        int index = L;
        while (index < R){
            if(arr[index] <= arr[R]){
                swap(arr, index, ++lessEqual);
            }
            index++;
        }
        swap(arr, ++lessEqual , R);
        return lessEqual;
    }

    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }


    /**
     *
     * < partition 在左边
     * = partition 在中间
     * > partition 在右边
     */
    public static void quickSort2(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        process2(arr, 0, arr.length - 1);
    }

    private static void process2(int[] arr, int L, int R) {
        if(L >= R){
            return;
        }
        int[] M = partition2(arr, L, R);
        process2(arr, L,M[0]);
        process2(arr,M[1] ,R);
    }

    private static int[] partition2(int[] arr, int L, int R) {
        if(L > R){
            return new int[]{-1, -1};
        }
        if(L == R){
            return new int[]{L, R};
        }

        int lessEqual = L - 1;
        int moreEqual = R + 1;
        int index = L;
        int partition = arr[R];
        while (index < moreEqual){
            if(arr[index] < partition){
                swap(arr,++lessEqual,index++);
            }else if(arr[index] == partition){
                index++;
            }else {
                swap(arr,index, --moreEqual);
            }
        }
        return new int[]{lessEqual,moreEqual};
    }

    public static void main(String[] args) {
        int testTime = 500000;
        int maxValue = 100;
        int maxSize = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr);
            quickSort1(arr);
            quickSort2(arr2);
            if(!isEqual(arr, arr2)){
                succeed = false;
                printArray(arr);
                printArray(arr2);
            }
        }
        System.out.println(succeed?"Good!!":"Fuck!!");

        int[] arr = new int[]{22,1,3,4,55,1,22,55,22,3,9};
        quickSort2(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    private static boolean isEqual(int[] arr, int[] arr2) {
        if(arr == null && arr2 != null){
            return false;
        }
        if(arr2 == null && arr != null){
            return false;
        }
        if(arr == null && arr2 == null){
            return true;
        }
        if(arr2.length != arr.length){
            return false;
        }
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] != arr2[i]){
                return false;
            }
        }
        return true;
    }

    private static void printArray(int[] arr) {
        if(arr == null){
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    private static int[] copyArray(int[] arr) {
        if(arr == null) {
            return new int[0];
        }
        int[] help = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            help[i] = arr[i];
        }
        return help;
    }

    private static int[] generateRandomArray(int maxSize, int maxValue) {
        int size = (int)(Math.random() * (maxSize + 1));
        int[] help = new int[size];
        for (int i = 0; i < size; i++) {
            help[i] = (int)(Math.random() * (maxValue + 1));
        }
        return help;
    }
}
